package _interview100;

import java.util.ArrayList;
import java.util.List;

/**
 * 300. 最长递增子序列
 */
public class No300 {

    private List<Integer> path;

    public int lengthOfLIS(int[] nums) {
        this.path = new ArrayList<>();

        for (int num : nums) {
            int index = lowerBound(num);
            if (index == path.size()) path.add(num);
            else path.set(index, num);
        }

        return path.size();
    }

    private int lowerBound(int target) {
        int left = 0, right = path.size() - 1;
        while (left <= right) {
            int mid = left + (right - left >> 1);
            if (path.get(mid) < target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
}
